import java.io.*;
import java.util.*;

public class 单源最短路径 {
    public static PrintWriter out = new PrintWriter(
            new BufferedWriter(new OutputStreamWriter(System.out)));
    public static Read in = new Read();
    public static int MAXN = 100001;
    public static int MAXM = 200001;
    public static int[] head = new int[MAXN];
    public static int[] next = new int[MAXM];
    public static int[] to = new int[MAXM];
    public static int[] weight = new int[MAXM];
    public static int n;
    public static int m;
    public static int cnt = 1;
    public static void main(String[] args) throws IOException{
        n = in.nextInt();
        m = in.nextInt();
        int s = in.nextInt();
        // 链式前向星建图
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            addEdge(a,b,c);
        }
        // 建立 distance 和 vis
        int[] distance = new int[n + 1];
        Arrays.fill(distance,Integer.MAX_VALUE);
        boolean[] vis = new boolean[n + 1];
        // 源点的距离标记
        distance[s] = 0;
        // 堆的建立以及加入源点
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        heap.offer(new int[]{s,0});
        while (!heap.isEmpty()) {
            // 弹出第一个点, 获取到达点的值
            int u = heap.poll()[0];
            if (vis[u]) {
                continue;
            }
            vis[u] = true;
            // 遍历图更新 distance 并加入堆中
            for (int i = head[u]; i != 0; i = next[i]) {
                int a = to[i]; // 到达点
                int b = weight[i]; // 距离
                // 没访问过并且要小于到达点的距离
                if (!vis[a] && distance[u] + b < distance[a]) {
                    distance[a] = distance[u] + b;
                    heap.offer(new int[]{a, distance[a]});
                }
            }
        }
        // 打印
        for (int i = 1; i <= n; i++) {
            out.print(distance[i] + " ");
        }
        out.close();
    }

    private static void addEdge(int a, int b, int c) {
        next[cnt] = head[a];
        head[a] = cnt;
        to[cnt] = b;
        weight[cnt++] = c;
    }


    public static class Read{
        StringTokenizer st = new StringTokenizer("");
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String next() throws IOException
        {
            while(!st.hasMoreTokens())
            {
                st = new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }

        String nextLine() throws IOException
        {
            return bf.readLine();
        }

        int nextInt() throws IOException
        {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException
        {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException
        {
            return Double.parseDouble(next());
        }
    }
}
